//
// Created by Bianwy on 2024/2/7.
//
#include <iostream>
#include <vector>

using namespace std;
// 155. 最小栈
// 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
// 实现 MinStack 类:
// MinStack() 初始化堆栈对象。
// void push(int val) 将元素val推入堆栈。
// void pop() 删除堆栈顶部的元素。
// int top() 获取堆栈顶部的元素。
// int getMin() 获取堆栈中的最小元素。
#define MaxSize 1000    // 若是定义太小了，会通过不了所有测试用例
class MinStack {
private:
    int data[MaxSize];      // 存放主栈中的元素，初始为空
    int mindata[MaxSize];   // 存放 mindata 辅助栈中的元素，初始为空
    int datatop;
    int mintop;
private:
    // mindata栈简化的基本运算算法，设为私有
    bool minempty()
    {
        return mintop == -1;
    }
    void minpush(int e)
    {
        mintop++;
        mindata[mintop] = e;
    }
    void minpop()
    {
        mintop--;
    }
    int mingettop()
    {
        return mindata[mintop];
    }
public:
    MinStack() {
        datatop = -1;
        mintop = -1;
    }

    bool empty()
    {
        return datatop == -1;
    }
    void push(int val) {
        // 主栈满则返回
        if(datatop >= MaxSize - 1)
            return;
        // 主栈为空或者 val <= mindata栈顶元素时，进mindata栈
        if(empty() || val <= getMin())
            minpush(val);
        datatop++;
        data[datatop] = val;    //将 val 进主栈
    }
    void pop() {
        if(empty())
            return;
        int x = data[datatop];  // 主栈的栈顶元素出栈
        datatop--;
        if(x == mingettop())    // 若栈顶元素为最小元素
            minpop();           // mindata出栈一次
    }

    int top() {
        if(empty())
            return INT_MIN;
        return data[datatop];
    }

    int getMin() {
        return mingettop();
    }
};

int main() {
    auto *minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    cout << minStack->getMin() << endl; // 返回-3
    minStack->pop();
    cout << minStack->top() << endl;    // 返回0
    cout << minStack->getMin() <<endl;  // 返回-2
    return 0;
}
